#pragma once

#include <cstddef>
#include <iostream>
#include <iterator>
#include <memory>

#include "ezstl_allocator.hpp"
#include "ezstl_construct.hpp"
#include "ezstl_iterator_base.hpp"

namespace ezstl {

template <typename T>
struct _ListNode {
  using value_type = T;
  _ListNode() : data{}, prev(nullptr), next(nullptr) {}
  _ListNode(const T &value) : data{value}, prev(nullptr), next(nullptr) {}
  _ListNode(T &&value) : data{std::move(value)}, prev(nullptr), next(nullptr) {}

  T data;
  _ListNode<T> *prev;
  _ListNode<T> *next;
};

template <typename T>
struct _ListIterator {
 public:
  using value_type = T;
  using pointer = value_type *;
  using const_pointer = const value_type *;
  using reference = value_type &;
  using const_reference = const value_type &;
  using iterator_category = ezstl::bidirectional_iterator_tag;

  using Node = _ListNode<T>;
  using iterator = _ListIterator<T>;

 public:
  _ListIterator() : m_pNode(nullptr) {}
  _ListIterator(Node *const pNode) : m_pNode(pNode) {}
  _ListIterator(const iterator &other) : m_pNode(other.m_pNode) {}

 public:
  reference operator*() const { return m_pNode->data; }
  pointer operator->() const { return static_cast<pointer>(&m_pNode->data); }
  bool operator==(const iterator &other) const {
    return m_pNode == other.m_pNode;
  }
  bool operator!=(const iterator &other) const { return !(*this == (other)); }
  iterator &operator++() {
    m_pNode = m_pNode->next;
    return *this;
  }
  iterator operator++(int) {
    iterator it = *this;
    ++(*this);
    return it;
  }
  iterator &operator--() {
    m_pNode = m_pNode->prev;
    return *this;
  }
  iterator operator--(int) {
    iterator it = *this;
    --(*this);
    return it;
  }

 public:
  Node *m_pNode;
};

template <typename T, typename Allocator = Allocator<_ListNode<T>>>
class List {
 public:
  using value_type = T;
  using allocator_type = Allocator;
  using size_type = std::size_t;
  using pointer = value_type *;
  using reference = value_type &;
  using const_reference = const value_type &;
  using iterator_category = ezstl::bidirectional_iterator_tag;

  using Node = _ListNode<T>;
  using Node_pointer = Node *;
  using iterator = _ListIterator<T>;
  using const_iterator = iterator;

 public:
  void show() {
    /*     for (iterator it = begin(); it != end(); ++it) {
          std::cout << *it << " ";
        }
        std::cout << std::endl; */
    for (auto &val : *this) {
      std::cout << val << " ";
    }
    std::cout << "size: " << size() << std::endl;
  }

 public:
  List &operator=(const List &other) {
    if (this == &other) return *this;
    clear();
    insert(begin(), other.begin(), other.end());
    return *this;
  }

  List &operator=(List &&other) {
    *this = std::move(other);
    return *this;
  }
  void assign(size_type count, const value_type &value);
  template <class InputIt>
  void assign(InputIt first, InputIt last);

  // Constructor
  List() {
    m_pDummy = allocate();
    m_pDummy->next = m_pDummy;
    m_pDummy->prev = m_pDummy;
    m_size = 0;
  }
  List(size_type count, const value_type &value) : List() {
    insert(begin(), count, value);
  }
  List(size_type count) : List(count, value_type{}) {}
  template <typename InputIt>
  List(InputIt first, InputIt last) : List() {
    insert(begin(), first, last);
  }
  List(const List &other) : List(other.begin(), other.end()) {}
  List(List &&other) {
    m_pDummy = other.m_pDummy;
    m_size = other.m_size;

    other.m_pDummy = nullptr;
    other.m_size = 0;
  }

  // Destructor
  ~List() {
    clear();
    dallocate(m_pDummy);
  }

  // Element access
  reference front() { return /* *begin(); */ m_pDummy->next->data; }
  const_reference front() const { return m_pDummy->next->data; }
  reference back() { return m_pDummy->prev->data; }
  const_reference back() const { return m_pDummy->prev->data; }

  // Iterators
  iterator begin() { return iterator{m_pDummy->next}; }
  const_iterator begin() const { return iterator{m_pDummy->next}; }
  const_iterator cbegin() const { return iterator{m_pDummy->next}; }
  iterator end() { return m_pDummy; }
  const_iterator end() const { return m_pDummy; }
  const_iterator cend() const { return m_pDummy; }

  // Capacity
  bool empty() const { return begin() == end(); };
  size_type size() const { return m_size; }

  // Modifiers
  void clear() {
    while (!empty()) erase(begin());
  }
  iterator insert(const_iterator pos, const value_type &value) {
    Node_pointer newNode = createNode(value);
    newNode->prev = pos.m_pNode->prev;
    newNode->next = pos.m_pNode;
    pos.m_pNode->prev->next = newNode;
    pos.m_pNode->prev = newNode;
    m_size++;
    return {newNode};
  }
  iterator insert(const_iterator pos, value_type &&value) {
    return emplace(pos, std::move(value));
  }
  iterator insert(const_iterator pos, size_type count,
                  const value_type &value) {
    if (count == 0) return pos;
    iterator it = pos;
    for (size_type i = 0; i < count; ++i) it = insert(it, value);
    return it;
  }
  template <typename InputIt>
  iterator insert(const_iterator pos, InputIt first, InputIt last) {
    if (first == last) return pos;
    iterator it = pos;
    for (; first != last; ++first) it = insert(it, *first);
    return it;
  }
  template <typename... Args>
  iterator emplace(const_iterator pos, Args &&...args) {
    Node_pointer newNode = createNode(std::forward<Args>(args)...);
    newNode->prev = pos.m_pNode->prev;
    newNode->next = pos.m_pNode;
    pos.m_pNode->prev->next = newNode;
    pos.m_pNode->prev = newNode;
    m_size++;
    return {newNode};
  }
  iterator erase(iterator pos) {
    Node_pointer next = pos.m_pNode->next;
    pos.m_pNode->prev->next = next;
    next->prev = pos.m_pNode->prev;
    --m_size;
    ezstl::destroy(&*pos);
    dallocate(pos.m_pNode);
    return iterator{next};
  }
  iterator erase(iterator first, iterator last) {
    if (first == last) return last;
    iterator it = first;
    while (it != last) it = erase(it);
    return it;
  }
  void push_back(const value_type &value) { insert(end(), value); }
  void push_back(value_type &&value) { emplace(end(), std::move(value)); }
  template <typename... Args>
  void emplace_back(Args &&...args) {
    emplace(end(), std::forward<Args>(args)...);
  }
  void pop_back() { erase(--end()); }
  void push_front(const value_type &value) { insert(begin(), value); }
  template <typename... Args>
  reference emplace_front(Args &&...args) {
    emplace(begin(), std::forward<Args>(args)...);
    return front();
  }
  void pop_front() { erase(begin()); }
  void resize(size_type count) { resize(count, value_type{}); }
  void resize(size_type count, const value_type &value) {
    if (count == size()) return;
    if (count < size()) {
      size_type toErase = size() - count;
      for (; toErase > 0; --toErase, pop_back());
    } else {
      insert(end(), count - size(), value);
    }
  }
  void swap(List &other) {
    std::swap(m_pDummy, other.m_pDummy);
    std::swap(m_size, other.m_size);
  }

  // Operations
  void merge(List &other) {
    if (this == &other) return;
    iterator f1 = begin();
    iterator l1 = end();
    iterator f2 = other.begin();
    iterator l2 = other.end();
    while (f1 != l1 && f2 != l2) {
      if (*f2 < *f1) {
        iterator next = f2;
        transfer(f1, f2, ++next);
        f2 = next;
      } else
        ++f1;
    }
    if (f2 != l2) transfer(l1, f2, l2);
    m_size += other.m_size;
    other.m_size = 0;
  }
  void merge(List &&other);  // TODO: merge rvalue
  void splice(const_iterator pos, List &other) {
    transfer(pos, other.begin(), other.end());
    m_size += other.m_size;
    other.m_size = 0;
  }
  void splice(const_iterator pos, List &&other);  // TODO: splice rvalue
  // 将it元素移动到pos之前
  void splice(const_iterator pos, List &other, const_iterator it) {
    auto j = it;
    ++j;
    if (pos == it || pos == j) return;
    transfer(pos, it, j);
    --other.m_size;
    ++m_size;
  }
  void splice(const_iterator pos, List &&other, const_iterator it);
  void splice(const_iterator pos, List &other, const_iterator first,
              const_iterator last) {
    if (first != last) {
      transfer(pos, first, last);
      m_size += other.m_size;
      other.m_size = 0;
    }
  }
  void splice(const_iterator pos, List &&other, const_iterator first,
              const_iterator last);
  void reverse() {
    if (size() == 0 || size() == 1) return;
    iterator first = begin();
    ++first;
    while (first != end()) {
      iterator old = first;
      ++first;
      transfer(begin(), old, first);
    }
  }

  void sort() {
    // sort(std::less<value_type>);
    sort([](const value_type &a, const value_type &b) { return a < b; });
  }

  template <typename Compare>
  void sort(Compare comp) {
    if (size() == 0 || size() == 1) return;
    List carry;
    List counter[64];
    int fill = 0;
    while (!empty()) {
      carry.splice(carry.begin(), *this, begin());
      int i = 0;
      while (i < fill && !counter[i].empty()) {
        counter[i].merge(carry);
        carry.swap(counter[i++]);
      }
      carry.swap(counter[i]);
      if (i == fill) ++fill;
    }
    for (int i = 1; i < fill; ++i) counter[i].merge(counter[i - 1]);
    swap(counter[fill - 1]);
  }

 protected:
  // 将[first, last) 移动到pos之前
  void transfer(iterator pos, iterator first, iterator last) {
    if (pos != last) {
      last.m_pNode->prev->next = pos.m_pNode;
      first.m_pNode->prev->next = last.m_pNode;
      pos.m_pNode->prev->next = first.m_pNode;

      Node_pointer tmp = pos.m_pNode->prev;
      pos.m_pNode->prev = last.m_pNode->prev;
      last.m_pNode->prev = first.m_pNode->prev;
      first.m_pNode->prev = tmp;
    }
  }

 private:
  Node_pointer allocate() { return Allocator::allocate(1); }
  void dallocate(Node_pointer p) { Allocator::deallocate(p); }

  Node_pointer createNode(const value_type &value) {
    Node_pointer newNode = allocate();
    new (newNode) Node(value);
    return newNode;
  }
  template <typename... Args>
  Node_pointer createNode(Args &&...args) {
    Node_pointer newNode = allocate();
    new (newNode) Node(std::forward<Args>(args)...);
    return newNode;
  }

 private:
  Node *m_pDummy;
  size_type m_size;
};

}  // namespace ezstl
